#ifndef __GGEAR_LINKED_LIST_H
#define __GGEAR_LINKED_LIST_H

#include "ggear_allocator.h"
#include "ggear_types.h"
#include "ggear_list.h"
#include "ggear_math.h"

namespace ggear
{
	namespace glb
	{
		template<class _Tx>
		class LinkedList : public List<_Tx>
		{
		private:
			struct ListNode
			{
				_Tx Value;
				ListNode* Next;
				ListNode* Previous;
				ListNode() : Next(null), Previous(null) {}
			};

		public:
			//list iterator
			class Iterator
			{
			friend class LinkedList<_Tx>;

			private:
				//Construct iterator from specific node
				Iterator(ListNode* _node) : mCurrent(node) {}

			public:
				//Destructor
				~Iterator() {}

				Iterator& operator ++ () { mCurrent = mCurrent->Next; return *this; }

				Iterator& operator -- () { mCurrent = mCurrent->Previous; return *this; }

				Iterator& operator += (s32 _step)
				{
					if(_step >= 0)
						for(s32 i = 0; i < _step && !mCurrent; i++, mCurrent = mCurrent->Next);
					else
						for(s32 i = 0; i > _step && !mCurrent; i--, mCurrent = mCurrent->Previous);
					return *this;
				}

				Iterator operator + (s32 _step)
				{
					Iterator res(mCurrent);
					res += _step;
					return res;
				}

				Iterator& operator -= (s32 _step) { return (*this += (-_step)); }

				Iterator operator - (s32 _step) { return (*this + (-_step)); }

				_Tx& operator * () { return mCurrent->Value; }

				_Tx* operator -> () { return &mCurrent->Value; }

				_Tx& operator [] (u32 _idx) { return (*this + _idx).mCurrent->Value; }

			private:
				ListNode* mCurrent;
			};

			//iterator for constant access
			class ConstIterator
			{
			friend class LinkedList<_Tx>;

			private:
				//Construct constant iterator from specific node
				ConstIterator(ListNode* _node) : mCurrent(_node) {}

			public:
				//Destructor
				~ConstIterator() {}

				ConstIterator& operator ++ () { mCurrent = mCurrent->Next; return *this; }

				ConstIterator& operator -- () { mCurrent = mCurrent->Previous; return *this; }

				ConstIterator& operator += (s32 _step)
				{
					if(_step >= 0)
						for(s32 i = 0; i < _step && !mCurrent; i++, mCurrent = mCurrent->Next);
					else
						for(s32 i = 0; i > _step && !mCurrent; i--, mCurrent = mCurrent->Previous);
					return *this;
				}

				ConstIterator operator + (s32 _step)
				{
					ConstIterator res(mCurrent);
					res += _step;
					return res;
				}

				ConstIterator& operator -= (s32 _step) { return (*this += (-_step)); }

				ConstIterator operator - (s32 _step) { return (*this + (-_step)); }

				const _Tx& operator * () { return mCurrent->Value; }

				const _Tx* operator -> () { return &mCurrent->Value; }

				const _Tx& operator [] (u32 _idx) { return (*this + _idx).mCurrent->Value; }

			private:
				ListNode* mCurrent;
			};

		public:
			//Default constructor
			LinkedList() 
				: mHead(null), mTail(null), mSize(0)
			{}

			//Destructor
			~LinkedList()
			{
				Clear();
			}


			//Check whether list is empty
			bool Empty() const
			{
				return (mSize == 0);
			}


			//Return number of elements in current list
			u32 Count() const
			{
				return mSize;
			}


			//Return value of element at specified position
			const _Tx& Get(u32 _pos) const
			{
				if(_pos >= mSize) throw "Exception";
				
				ListNode* cur = mHead;
				for(u32 i = 0; i < _pos; i++ , cur = cur->Next);
				return cur->Value;
			}


			//Set value of element at specified position
			void Set(const _Tx& _val, u32 _pos)
			{
				if(_pos >= mSize) throw "Exception";

				ListNode* cur = mHead;
				for(u32 i = 0; i < _pos; i++, cur = cur->Next);
				cur->Value = _val;
			}


			//Insert new element at specified position in current list
			void Insert(const _Tx& _val, u32 _pos)
			{
				if(_pos > mSize) throw "Exception";

				if(!mSize || !_pos)
				{
					PushFront(_val);
				}
				else if(_pos < mSize)
				{
					ListNode* node = new ListNode();
					node->Value = _val;

					//get the list node at _pos
					ListNode* cur = mHead;
					for(u32 i = 0; i < _pos; i++, cur = cur->Next);
					node->Next = cur;
					node->Previous = cur->Previous;
					cur->Previous->Next = node;
					cur->Previous = node;

					mSize++;
				}
				else
				{
					PushBack(_val);
				}
			}


			void PushFront(const _Tx& _val) 
			{ 
				ListNode* node = new ListNode();
				node->Value = _val;
				if(!mSize)
				{
					mHead = mTail = node;
				}
				else
				{	
					mHead->Previous = node;
					node->Next = mHead;
					mHead = node;
				}
				mSize++;
			}


			void PushBack(const _Tx& _val) 
			{
				ListNode* node = new ListNode();
				node->Value = _val;
				if(!mSize)
				{
					mHead = mTail = node;
				}
				else
				{	
					mTail->Next = node;
					node->Previous = mTail;
					mTail = node;
				}
				mSize++; 
			}


			//Delete an element at specified position in current list
			void Remove(u32 _pos)
			{
				if(_pos >= mSize)
					throw "Exception";
				
				if(!_pos)
				{
					PopFront();
				}
				else if (_pos < mSize - 1)
				{
					ListNode* node = mHead->Next;
					for(u32 i = 1; i < _pos; i++, node = node->Next);
					mSize--;

					ListNode* prevNode = node->Previous;
					ListNode* nextNode = node->Next;
					nextNode->Previous = prevNode;
					prevNode->Next = nextNode;	
					delete node;
				}
				else
				{
					PopBack();
				}
			}


			void PopFront()	
			{ 
				if(!mSize) return;
				ListNode* node = mHead;
				mSize--;

				if(!mSize)
				{
					//if there is only one node in the list
					mHead = mTail = null;
				}
				else
				{
					mHead = node->Next;
					mHead->Previous = null;
					node->Next = null;
				}
				delete node;

			}


			void PopBack() 
			{
				if(!mSize) return;
				ListNode* node = mTail;
				mSize--;

				if(!mSize)
				{
					//if there is only one node in the list
					mHead = mTail = null;
				}
				else
				{
					mTail = node->Previous;
					mTail->Next = null;
					node->Previous = null;
				}
				delete node;
			}
			

			//Delete all element inside current list
			void Clear()
			{
				ListNode* node = mHead;
				ListNode* nnode = mHead->Next;
				while(!isnull(node))
				{
					if(!isnull(nnode))
					{
						nnode->Previous = null;
						node->Next = null;
					}
					delete node;
					node = nnode;
					nnode = isnull(nnode) ? null : nnode->Next;
				}
			}


			Iterator Begin() { return Iterator(mHead); }


			Iterator End() { return Iterator(mTail); }


			ConstIterator Begin() const { return ConstIterator(mHead); }


			ConstIterator End() const { return ConstIterator(mTail); }


			//Swap value between 2 elements inside current list
			void Swap(u32 _lpos, u32 _rpos)
			{
				if(_lpos == _rpos || _lpos >= mSize || _rpos >= mSize) 
					return;

				ListNode* ln = null;
				ListNode* rn = null;
				u32 lidx = _lpos < _rpos ? _lpos : _rpos;
				u32 ridx = _rpos > _lpos ? _rpos : _lpos;

				if((mSize <= (2*ridx - lidx + 1)) && (2*lidx - ridx <= 0)) //search from both side
				{
					ln = mHead;
					rn = mTail;
					for(u32 i = 0; i < lidx; i++, ln = ln->Next);
					for(u32 i = mSize - 1; i > ridx; rn = rn->Previous);
				}
				else
				{
					if(ridx  + lidx + 1 <= mSize) //search from left to right
					{
						u32 count = 0;
						for(ln = mHead; count < lidx; count++, ln = ln->Next);
						for(rn = ln;count < ridx; count++, rn = rn->Next);
					}
					else //search from right to left
					{
						u32 count = mSize - 1;
						for(rn = mTail; count > ridx; count--, rn = rn->Previous);
						for(ln = rn; count > lidx; count--, ln = ln->Previous);
					}
				}
				//swap values of 2 nodes
				_Tx tmp = ln->Value;
				ln->Value = rn->Value;
				rn->Value = tmp;
			}

			//Get or set value of element at specified position
			_Tx& operator [] (s32 _pos)
			{
				if(_pos >= mSize)
					throw "Exception";
				ListNode* cur = mHead;
				for(u32 i = 0; i < _pos; i++ , cur = cur->Next);
				return cur->Value;
			}

			const _Tx operator [] (s32 _pos) const
			{
				return Get(_pos);
			}

		private:
			ListNode* mHead;
			ListNode* mTail;
			u32	mSize;
		};
	}
}

#endif//__GGEAR_LINKED_LIST_H